package com.practice.math;

import java.util.ArrayList;

public class Multiplication {
	public String multiply(String a, String b) {
		ArrayList<Integer> la = convert(a);
		ArrayList<Integer> lb = convert(b);
		
		ArrayList<Integer> lc = new ArrayList<Integer>();
		for (int i=0; i<la.size()+lb.size(); i++) lc.add(0);
		
		for (int i=0; i<la.size(); i++) {
			int remainder = 0;
			for (int j=0; j<lb.size(); j++) {
				int s = lc.get(i+j) + la.get(i)*lb.get(j) + remainder;
				lc.set(i+j, s%1000);
				remainder = s/1000;
			}
			
			if (remainder > 0) lc.set(i+lb.size(), remainder);
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i : lc) {
			sb.insert(0, String.format("%03d", i));
		}
		return sb.toString().replaceAll("^0*", "").trim();
	}
	
	private ArrayList<Integer> convert(String a) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		int i;
		for (i=a.length(); i>=3; i-=3) {
			list.add(Integer.parseInt(a.substring(i-3, i)));
		}
		if (i > 0) list.add(Integer.parseInt(a.substring(0, i)));
		return list;
	}
}
